#include <string>
#include <vector>
#include <sstream>
#include <unordered_map>
#include <iostream>

using namespace std;

/*
AABBC ->
key: char
value: int
对于一个字典来说，它有可能包含重复的 key 么？
unordered_map<char, int>
{
  'A': 2,
  'B': 2,
  'C': 1
}
*/
string statEncoding(const string &str) {
  unordered_map<char, int> records;

  for (char c : str) {
    // 字符 c 是不是已经在 records 里了？
    // 如果有了？ 字符 c 的个数 + 1
    // 如果不在？ 创建一个新纪录，c 的个数是 1
    if (records.find(c) != records.end()) {
      records[c] += 1;
    }
    else {
      records[c] = 1;
    }
  }

  // records
  // 2A2B1C
  vector<char> keys; // str 中所有不重复的字母

  for (auto record : records) {
    keys.push_back(record.first);
  }

  sort(keys.begin(), keys.end());

  ostringstream result;
  for (char k : keys) {
    result << records[k] << k;
  }

  return result.str();
}

int main(int argc, char const *argv[])
{
  /* code */
  cout << statEncoding("AABBC") << endl;
  return 0;
}
